<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<link href="CSS/main.css" rel="stylesheet" type="text/css" />
<link href="CSS/style3.css" rel="stylesheet" type="text/css" />
<link href="CSS/Layer.css" rel="stylesheet" type="text/css" />
<title>Comparing with LPA* - hoangvp 2010</title>
</head>

<body>
<script type="text/javascript" src="JS/priority_queue.js"></script>
<script type="text/javascript" src="JS/MathHelpers.js"></script>
<script type="text/javascript" src="JS/AJAX.js"></script>
<script type="text/javascript" src="JS/DOM.js"></script>
<script type="text/javascript" src="JS/layer.js"></script>
<?php
require_once 'Map.class.php';

$x = new Map("map.txt");
$x->printMap();
$x->generateJSCode();
generateJSDebugCode($DEBUG_);

if($DEBUG_){
	echo '
	<script type="text/javascript">
	function traceClosedDebug(x, y, newPreX, newPreY, oldCost, newCost){
		var s = "Current ("+oldCost+"): ";
		var x1 = x, y1 = y;
		s+= "(" + x + ", " + y + ")";
		while(x != globalStart.x || y != globalStart.y){
			var t = traceMap[x][y];
			x = t.x;
			y = t.y;
			s+= " <- (" + x + ", " + y + ")";
		}
		s+= "\nNow ("+newCost+"): (" + x1 + ", " + y1 + ") <- (" + newPreX + ", " + newPreY + ") ";
		x = newPreX;
		y = newPreY;
		while(x != globalStart.x || y != globalStart.y){
			var t = traceMap[x][y];
			x = t.x;
			y = t.y;
			s+= "<- (" + x + ", " + y + ")";
		}
		s+= "\n";
		log(s);
	}
	</script>
	';		
}
?>

<script type="text/javascript">
heuristicFunction = diagonalAndEuclid;

var importanceOfHeuristic = 1;

function isBetter(a, b){
	var ha = a.heuristic * importanceOfHeuristic;
	var hb = b.heuristic * importanceOfHeuristic;
	var suma = a.cost + ha;
	var sumb = b.cost + hb;
	if(suma < sumb){
		return BETTER;
	} else if(suma == sumb){
		if(ha < hb){		//TIE BREAKING
			return BETTER;
		}
	}
	return WORSE;	
}

function aStarDistance(){
	while(!queue.isEmpty()){
		++loopsCount;			
		var t = queue.pop();
		t.status = IN_CLOSED_SET;
		setTimeout('fillRed('+t.x+', '+t.y+');', SPEED*loopsCount);				
		if(isFinish(t) == true){
			return true;
		} else if(t.cost == INFINITY){
			return false;
		} else {
			//logDebug("Xét ô (" + (t.x) + ", " + (t.y) + ")");
			for(var i=startIndex; i<aroundLength; ++i){
				var x = t.x + around[i][0];
				var y = t.y + around[i][1];
				//logDebug("\tXét lân cận là ô ("+x+", "+y+") => Tới được = " + doesPathExist(t.x, t.y, x, y));
				if(doesPathExist(t.x, t.y, x, y)){
					var cell = map[x][y];							
					var oldCost = cell.cost;
					var newCost = getExactNumDigits(t.cost + costToMove(t.x, t.y, x, y), 2);
					//logDebug("Chi phí cũ = "+oldCost + ", chi phí mới = " + newCost + " => Cũ>Mới = " + (oldCost > newCost));
					if(cell.status == IN_OPEN_SET && oldCost > newCost){
						//logDebug("\t"+x + " " + y + " nằm trong tập OPEN!");
						cell.cost = newCost;													
						traceMap[x][y] = t;
					} else if(cell.status == IN_CLOSED_SET && oldCost > newCost){
						//logDebug("\t"+x + " " + y + " nằm trong tập CLOSED!");
						traceClosedDebug(x, y, t.x, t.y, oldCost, newCost);
						cell.cost = newCost;
						queue.push(cell);
						cell.status = IN_OPEN_SET;
						traceMap[x][y] = t;
					} else if(cell.status != IN_CLOSED_SET && cell.status != IN_OPEN_SET){								
						if(oldCost > newCost){
							cell.cost = newCost;
							queue.push(cell);
							cell.status = IN_OPEN_SET;
							traceMap[x][y] = t;
							//logDebug("Đưa "+x + " " + y + " vào tập OPEN với chi phí = " + newCost);
						}
						setTimeout('fillYellow('+x+', '+y+');', SPEED*loopsCount + DELAY);
					}
					setTimeout('setG('+x+', '+y+', '+cell.cost+');setF('+x+', '+y+', '+(cell.cost + cell.heuristic)+');', SPEED*loopsCount + DELAY);					
					++expandCount;
				}
			}
			queue.adjust();									
		}
	}
	return false;
}

function aStarStep(){
	while(!queue.isEmpty()){
		++loopsCount;			
		var t = queue.pop();
		t.status = IN_CLOSED_SET;
		setTimeout('fillRed('+t.x+', '+t.y+');', SPEED*loopsCount);
		if(isFinish(t) == true){
			return true;
		} else if(t.cost == INFINITY){
			return false;
		} else {
			//alert("Examine node (" + (t.x+1) + ", " + (t.y+1) + ") <br/>");
			for(var i=startIndex; i<aroundLength; ++i){
				var x = t.x + around[i][0];
				var y = t.y + around[i][1];
				if(doesPathExist(t.x, t.y, x, y)){
					var cell = map[x][y];
					if(cell.status != IN_CLOSED_SET && cell.status != IN_OPEN_SET){
						setTimeout('fillYellow('+x+', '+y+');', SPEED*loopsCount + DELAY);
						var newCost = t.cost + 1;
						if(cell.cost > newCost){
							cell.cost = newCost;
							queue.push(cell);
							cell.status = IN_OPEN_SET;
							setTimeout('setG('+x+', '+y+', '+cell.cost+');setF('+x+', '+y+', '+(cell.cost + cell.heuristic)+');', SPEED*loopsCount + DELAY);
							traceMap[x][y] = t;
							++expandCount;
						}
					}
				}
			}
		}
		queue.adjust();
	}
	return false;
}

function astar(start, finish){
	var startTime = new Date();
	globalStart = start;
	globalFinish = finish;
	var found  = false;	
	var loopsCount = 0;	
	expandCount = 0;
	if(walkable(start.x, start.y) && walkable(finish.x, finish.y)) {
		//Init
		map[start.x][start.y].cost = 0;
		queue = new PriorityQueue({cmpFunc : isBetter});
		queue.push(map[start.x][start.y]);			
		traceMap = new Array();
		for(var i=0; i<m; ++i){				
			traceMap[i] = new Array(n);			
		}

		//queue.adjust();queue.display();
		
		//Main loop
		if(costIsDistance){
			found = aStarDistance();
		} else {
			found = aStarStep();
		}
	}	

	//Trace path
	var finishTime = new Date();
	tracePath(found, traceMap, loopsCount);	
	statistic(++turn, finish.cost, loopsCount, expandCount, finishTime.getTime() - startTime.getTime());
}

function search(){
	heuristicWasInitialized = false;
	if(turn > 0){	
		clearMap();
	}
	var f = document.route;
	var fx = eval(f.fromX.value);
	var fy = eval(f.fromY.value);
	var tx = eval(f.toX.value);
	var ty = eval(f.toY.value);
	//alert(fx + " " + fy + "\n" + tx + " " + ty);	
	if(!heuristicWasInitialized){
		initHValue(tx, ty);
	}
	astar(map[fx][fy], map[tx][ty]);	
}

function changeTerrain(a){
	if(a){
		beginChangeTerrain();	
	} else {
		endChangeTerrain();
	}
}

function beginChangeTerrain(){
	setAllWallCells();
	document.searchFrm.searchBtn.disabled = "disabled";	
}

var onclickFuncs = [];
function setAllWallCells(){
	if(document.searchFrm.changeBtn.checked){
		for(var i=0; i<m; ++i){
			onclickFuncs[i] = [];
			for(var j=0; j<n; ++j){
				var t = getMapCell(i, j);
				onclickFuncs[i][j] = t.getAttribute("onclick");
				t.setAttribute("onclick", "toogleCell("+i+", "+j+");");				
			}
		}
	} else {
		for(var i=0; i<m; ++i){
			for(var j=0; j<n; ++j){
				getMapCell(i, j).setAttribute("onclick", onclickFuncs[i][j]);
			}
		}
	}
}

function toogleCell(x, y){	
	var t = getMapCell(x, y);
	if(t.className == "wall"){
		t.className = "";
		terrain[x][y] = 0;
	} else {
		t.className = "wall";
		terrain[x][y] = 1;
	}
}

function endChangeTerrain(){	
	setAllWallCells();
	document.searchFrm.searchBtn.disabled = "";	

	var s = "";
	for(var i=0; i<m; ++i){
		for(var j=0; j<n; ++j){
			s += terrain[i][j] + " ";
		}
		s += "\n";
	}
	log(s);
}

//CLEAR MAP FUNCTION
function clearMap(){
	while(!queue.isEmpty()){
		queue.pop();
	}
	for(var i=0; i<m; ++i){
		for(var j=0; j<n; ++j){
			var t = getMapCell(i, j);
			t.style.backgroundColor = "#FFF";
			if(terrain[i][j]){				
				t.className = "wall";
			} else {
				if(t.className != "start" && t.className != "finish"){
					t.className = "";
				}
			}
			if(t.childNodes.length > 0){
				t.childNodes[0].src = "";
			}
			var k = map[i][j];
			k.cost = INFINITY;
			k.heuristic = INFINITY;
			k.status = NEW;			
		}
	}
}

</script>
<form name="searchFrm">
	<input type="button" name="searchBtn" value="Bắt đầu" onclick="searchBtnOnclickFunc(this);" />
	<input type="button" name="resetBtn" value="Mới" onclick="window.location.reload();" /><br />
	<input type="checkbox" name="changeBtn" onclick="changeTerrain(this.checked);" /> Thay đổi bản đồ 
	<input type="button" name="saveBtn" value="Lưu bản đồ" onclick="save();" />
</form>
<div id="cost"></div>
<div>
<table id="statisticTable" border="1">
	<tr>
		<th>Lượt</th>		
		<th>Chi phí</th>
		<th>Số đỉnh được xét</th>
		<th>Số đỉnh được mở rộng</th>
		<th>Thời gian (miligiây)</th>
	</tr>
</table>
<textarea id="log" rows="30" cols="100"></textarea></div>
<script type="text/javascript">
document.searchFrm.searchBtn.disabled = "";
document.searchFrm.changeBtn.checked = false;
</script>
</body>
</html>